1. Field of the Invention
This invention relates to an arithmetic circuit for Montgomery multiplication and an encryption circuit for executing encryption and decryption processes using the arithmetic circuit for Montgomery multiplication.
2. Description of the Related Art
An electronic commercial transaction for signing a contract or settling an account using a network such as an internet is conducted by, for example, an electronic shop to sell commodities on the network (commercial transaction between enterprises and consumers). Through this electronic commercial transaction, the consumers can select a commodity by browsing a Web site of the electronic shop and purchase it by designating a method of settlement.
In this electronic commercial transaction, a problem is how to prevent an impersonation, wiretapping or alteration to maintain security. As an authentication technique for preventing the impersonation, for example, a public key cryptosystem is used. In the public key cryptosystem, two different keys are used for encryption and decryption, and it is very difficult or impossible to estimate the decryption key from the encryption key or decode the encrypted text. The key holder places the encryption key (public key) in public domain, and by managing the decryption key (private key) in a manner unknown to a third party, information on the other party of transaction using the public key can be kept confidential from the third party.
The commercial transaction between the electronic shop and the consumer described above, for example, is conducted in such a manner that the electronic shop places the encryption key (public key) in public domain and manages the decryption key (private key) in a way unknown to the third party. The consumer, using the encryption key (public key) placed in public domain by the electronic shop, encrypts and transmits information on the commercial transaction to the electronic shop. The encrypted text received from the consumer is decrypted by the electronic shop using the decryption key (private key) and the commodity is sold to the consumer. The electronic shop holding the key, by managing the decryption key (private key) in a manner unknown to the third party, can prevent both the information on the commercial transaction and personal information of the consumer from being leaked to the third party.
An example of the public key cryptosystem is a RSA (Rivest Shamir Adleman) cryptosystem. The decryption of the RSA cryptography requires the prime factorization of a very large integer, and cannot be accomplished within a realistic computation time even by the computer.
The RSA encryption and decryption methods are briefly explained below.
Assume that a plain text M is encrypted using a public key (e, n). An encrypted text C is generated according to Equation (1) below.C=Memodn(0≦M<n)  (1)
In a case where the encrypted text C is decrypted using a private key (d, n), on the other hand, the plain text M is generated according to Equation (2) below.M=Cdmodn  (2)
Incidentally, the public key (e, n) and the private key (d, n) hold the relation shown by Equation (3) below.n=p×q (p, q: prime number)e×d≡1 mod(p−1)(q−1)  (3)
Specifically, assume that p=3, q=11, e=3 and d=7. In the encrypted text C obtained by encrypting the plain text M (=7) is given as C=73mod(3×11)=343mod 33=13 from Equation (1).
Also, according to Equation (2), the plain text M obtained by decryption of the encrypted text C (=13) is given as M=137mod33=62748517mod33=7. It is therefore understood that the encryption and decryption according to Equations (1) and (2) are correctly carried out.
In the RSA cryptosystem described above, power calculation and surplus calculation are carried out as indicated by Equations (1) and (2). Generally, the key and the plain text have as large a number of digits of not less than 1024 bits, and therefore, an overflow may be caused if the encryption or decryption is carried out using Equations (1) and (2) as they are on an arithmetic unit.
In the encryption and decryption by the RSA cryptosystem, therefore, the Montgomery multiplication is used as an example of the surplus computation method which causes no overflow. In the Montgomery multiplication, the surplus calculation of N bits can be carried out in a N-bit memory space.
The Montgomery multiplication is explained briefly below.
A right side of the equation 1C=Me mod n of the RSA cryptosystem can be determined by the sequential calculation such as M2modn=M×Mmodn, M3modn=M×M2modn, . . . , Me modn=M×Me−1modn. In other words, the calculation is possible by repeating the operation γ=α×βmodn.
The Montgomery multiplication, which is carried out on the computer, uses a constant R =2N. Two sides of γ=α×βmodn are multiplied by R to determine modn, and then, the relation holds that γRmodn=αR×βR×R−1modn. Assume that Z=γRmodn, A=αRmodn and B=βRmodn. Then, the calculation for Montgomery multiplication is given by Equation (4) below.Z=A×B×R−1modn  (4)
FIG. 9 shows an example of a program code (pseudo code) for computation of the Montgomery multiplication of Equation (4) on the arithmetic unit.
In the RSA cryptosystem, the plain text M has so large a number of bits (1024 bits, etc.), and therefore, each of variables A, B, n for the Montgomery multiplication used in the encryption according to the RSA cryptosystem also has a very large number of bits. For the Montgomery multiplication to be conducted on the arithmetic unit, therefore, the variables A, B, n are required to be divided by a bit width r so as to be calculable by the arithmetic unit. Specifically, assume that the variables A, B, n have the same bit width, and define s as the number of divisions. Then, the relations hold that A={a[s−1], a[s−2], . . . , a[0]}, B={b[s−1], b[s−2], . . . , b[0]}, n={n[s−1], n[s−2], . . . , n[0]} and N=r×s.
Also, in FIG. 9, (C, S) indicates variables for storing the calculation result, in which the variable C indicates a most significant r bits of (C, S) and the variable S a least significant r bits of (C, S). On the other hand, t[s+1], t[s], . . . , t[0] and m indicate temporary variables of the bit width r.
As understood from FIG. 9, the calculation formula (C, S):=t[j]+a[j]*b[i]+C is located inside a subloop of a main loop and shows the greatest number of times the computation is made as indicated by ((s−1)×(s−1)). In order to increase a speed of encryption and decryption in the RSA cryptosystem, therefore, a computation of (C, S):=t[j]+a[j]*b[i]+C in the Montgomery operation is required to be increased in speed. Incidentally, the sign * in FIG. 9 designates the multiplication (×).
As an arithmetic unit for carrying out the Montgomery multiplication at a high speed, Japanese Unexamined Patent Publication No. 2002-207589, for example, proposes an arithmetic circuit including a calculator configured by first to fourth registers to store variables x1, x2, x3, x4, respectively, having a bit width r, a memory A configured by a two-port RAM (random access memory), a memory B configured by a two-port or one-port RAM, and a calculator adapted to accept the variables x1, x2, x3, x4 from the first to fourth registers, and by calculating the sum of the product of the variable x1, the variable x2 and the variable x3 and the variable x4, execute a pipelining process to output the calculation result Q of a bit width 2r or 2r+1, wherein after executing the pipelining process, a memory write process is executed to write data QL including the least significant r bits of the calculation result Q in the memory A and data QH including the most significant r bits of the calculation result in the fourth register, and wherein a memory read process is executed to read and output the variable x1 from the memory A to the first register and the variable x3 from the memory B to the third register.
FIG. 10 shows an example of a general configuration of the arithmetic circuit described in Japanese Unexamined Patent Publication No. 2002-207589. FIG. 11A shows a flow of a memory read process (memory read cycle) and a memory write process (memory write cycle) serially executed, and FIG. 11B shows a flow of a memory read process and a memory write process executed by pipelining in the configuration described in Japanese Unexamined Patent Publication No. 2002-207589 with the memory B configured by a two-port RAM.
As understood from FIGS. 11A and 11B, the arithmetic circuit described in Japanese Unexamined Patent Publication No. 2002-207589 can execute the memory read process and the memory write process by pipelining, and therefore, can increase an operation speed as compared with a case in which the memory read process and the memory write process are executed serially.
In a case where the Montgomery multiplication is carried out by an arithmetic circuit implemented by, for example, an ASIC (application specific integrated circuit), however, the two-port RAM often fails to be supported by a standard ASIC library. The two-port RAM, even if so supported, is sometimes limited to the one having a large area according to a 2-read/2-write system. From the viewpoint of circuit design standardization and the realization of IP (intellectual property), it is undesirable to use a two-port RAM often failing to be supported positively.